package com.monday.greedy.algorithm;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;

/**
 * 区域覆盖
 * 假设有 n 个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。
 * 从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？
 */
public class AreaCoverage {

    /**
     * 区域覆盖
     *  1、先按照右端点排序,右端点相同,再按左端点排序
     *  2、选择区域：每次选择右端点最小的区域,同时保证区域的左端点>=上一个区域的右端点
     */
    public void areaCoverage(Area[] areas) {
        //  1、先按照右端点排序,右端点相同,再按左端点排序
        Arrays.sort(areas, (a, b) -> (a.getEnd() == b.getEnd()) ? (a.getStart() - b.getStart()) : (a.getEnd() - b.getEnd()));
        System.out.println("==============排序后的区间:" + Arrays.toString(areas));

        int initStart = Integer.MIN_VALUE;
        for (Area area : areas) {
            if (area.getStart() >= initStart) {
                initStart = area.getEnd();
                System.out.println("选择区域:" + area);
            }
        }
    }

    @Data
    @Builder
    @NoArgsConstructor
    @AllArgsConstructor
    public static class Area {
        private int start;
        private int end;
        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }

}
